package daily_exercise;


import java.util.*;
import java.util.PriorityQueue;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class Demo1 {

    // 2617. 网格图中最少访问的格子数
    public int minimumVisitedCells(int[][] grid) {
        int n = grid.length, m = grid[0].length;

        // 1. 创建每一行和每一列的小根堆,存放下标
        PriorityQueue<int[]>[] rowHeaps = new PriorityQueue[n];     // int[]: 存放最少访问格子数和列下标
        for (int i = 0; i < n; i++) {
            rowHeaps[i] = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        }
        PriorityQueue<int[]>[] colHeaps = new PriorityQueue[m];     // int[]: 存放最少访问格子数和行下标
        for (int i = 0; i < m; i++) {
            colHeaps[i] = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        }

        // 2. 进行 dp
        int res = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int path = 0X3f3f3f3f;
                if (i == 0 && j == 0) path = 1;

                // 从该行 minHeap 找到最小值
                while (!rowHeaps[i].isEmpty()) {
                    int col = rowHeaps[i].peek()[1];
                    if (col + grid[i][col] < j) rowHeaps[i].poll();
                    else break;
                }
                if (!rowHeaps[i].isEmpty()) {
                    path = Math.min(path, rowHeaps[i].peek()[0] + 1);
                }
                // 从该列 minHeap 找到最小值
                while (!colHeaps[j].isEmpty()) {
                    int row = colHeaps[j].peek()[1];
                    if (row + grid[row][j] < i) colHeaps[j].poll();
                    else break;
                }
                if (!colHeaps[j].isEmpty()) {
                    path = Math.min(path, colHeaps[j].peek()[0] + 1);
                }

                // 如何能够到达该点，则加入该行和列的优先级队列中
                if (path < 0X3f3f3f3f) {
                    if (i == n - 1 && j == m - 1) res = path;
                    rowHeaps[i].offer(new int[]{path, j});
                    colHeaps[j].offer(new int[]{path, i});
                }
            }
        }

        return res;
    }


    // 2549. 统计桌面上的不同数字
    public int distinctIntegers(int n) {
        return n > 1 ? n - 1 : 1;
    }

    // 322. 零钱兑换
    public int coinChange(int[] coins, int amount) {
        // 一维背包的完全背包问题
        // dp[i][j]: 在前 i 个硬币中选择若干个硬币，恰好凑成金额为 j 所需的最少硬币数
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) dp[i] = 0X3f3f3f3f;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        return dp[amount] >= 0X3f3f3f3f ? -1 : dp[amount];
    }


    // 518. 零钱兑换 II
    public int change(int amount, int[] coins) {
        // 一维背包问题——完全背包
        // dp[i][j]: 在前 i 中硬币中选择若干个硬币，且恰好凑成金额为 j 的硬币组合数
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }


    // 2580. 统计将重叠区间合并成组的方案数
    public int countWays(int[][] ranges) {
        // 1. 对一维数组按第一个元素排序
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);

        // 2. 统计出有多少个含交集的区间
        int n = ranges.length;
        long res = 1;
        for (int i = 0, j = 0; i < n; ) {
            for (int end = ranges[i][1]; j < n && end >= ranges[j][0]; j++) {
                end = Math.max(end, ranges[j][1]);
            }
            res = res * 2 % 1_000_000_007;
            i = j;
        }

        return (int) res;
    }


    // 743. 网络延迟时间
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] time : times) {
            g[time[0] - 1].add(new int[]{time[1] - 1, time[2]});    // 下一结点和需花费的时间
        }

        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[k - 1] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // 节点i和dis[i]
        pq.offer(new int[]{k - 1, 0});

        int res = 0;
        while (!pq.isEmpty()) {
            int[] f = pq.poll();
            int i = f[0], v = f[1];     // 节点i和dis[i]

            if (dis[i] < v) continue;
            if (v > res) res = v;

            for (int[] time : g[i]) {
                if (v + time[1] < dis[time[0]]) {
                    dis[time[0]] = v + time[1];
                    pq.offer(new int[]{time[0], v + time[1]});
                }
            }
        }
        for (int x : dis) {
            if (x == Integer.MAX_VALUE) return -1;
        }
        return res;
    }


    // 2642. 设计可以求最短路径的图类
    class Graph {
        private final List<int[]>[] g;            // int[]: 记录邻接结点和对应的权值

        public Graph(int n, int[][] edges) {
            g = new ArrayList[n];
            Arrays.setAll(g, i -> new ArrayList<>());       // 为数组每个元素进行初始化

            for (int[] edge : edges) {
                g[edge[0]].add(new int[]{edge[1], edge[2]});
            }
        }


        public void addEdge(int[] edge) {
            g[edge[0]].add(new int[]{edge[1], edge[2]});
        }


        public int shortestPath(int start, int end) {
            int n = g.length;
            int[] dis = new int[n];
            Arrays.fill(dis, Integer.MAX_VALUE);
            dis[start] = 0;

            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);   // 存放 结点i和dis[i]
            pq.offer(new int[]{start, 0});

            while (!pq.isEmpty()) {
                int[] f = pq.poll();
                int d = f[0];   // 当前最小dis[i]对应的结点
                int m = f[1];   // dis[i]

                if (d == end) return m;                         // 计算出从起点到终点的最短路长度
                if (m > dis[d] || g[d].isEmpty()) continue;     // dis[d]在之前已经推出过，无需更新邻居的最短路

                for (int[] edge : g[d]) {
                    if (m + edge[1] < dis[edge[0]]) {           // 更新最短路长度
                        dis[edge[0]] = m + edge[1];
                        pq.offer(new int[]{edge[0], dis[edge[0]]});
                    }
                }
            }

            return -1;
        }
    }


    // 2908. 元素和最小的山形三元组 I
    public int minimumSum(int[] nums) {
        int n = nums.length, res = Integer.MAX_VALUE;
        // dp1[i]:在 i 位置之前所有元素的最小值
        // dp2[i]:在 i 位置之后所有元素的最小值
        int[] dp1 = new int[n], dp2 = new int[n];
        dp1[0] = dp2[n - 1] = 100;
        for (int i = 1; i < n; i++) dp1[i] = Math.min(dp1[i - 1], nums[i - 1]);
        for (int i = n - 2; i >= 0; i--) dp2[i] = Math.min(dp2[i + 1], nums[i + 1]);
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > dp1[i] && nums[i] > dp2[i]) {
                res = Math.min(res, nums[i] + dp1[i] + dp2[i]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }


    // 331. 验证二叉树的前序序列化
    public boolean isValidSerialization(String preorder) {
        Deque<Integer> stack = new ArrayDeque<>();

        char[] arr = preorder.toCharArray();
        int cur = 0, n = arr.length;
        for (; cur < n; cur++) {
            char ch = arr[cur];
            if (ch == ',') continue;

            if (ch != '#') { // 提取结点的值并入栈
                int num = 0;
                while (cur < n && arr[cur] != ',') num = num * 10 + arr[cur++] - '0';
                stack.push(num);
            } else {
                // 出栈
                if (stack.isEmpty()) break;
                stack.pop();
            }
        }
        return cur == n - 1;
    }


    // 1026. 节点与其祖先之间的最大差值
    private int ret = 0;
    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return ret;
    }
    private void dfs(TreeNode root, int parentMaxValue, int parentMinValue) {
        if (root == null) return;
        ret = Math.max(ret, Math.abs(root.val - parentMaxValue));
        ret = Math.max(ret, Math.abs(root.val - parentMinValue));
        if (root.val > parentMaxValue) parentMaxValue = root.val;
        if (root.val < parentMinValue) parentMinValue = root.val;
        dfs(root.left, parentMaxValue, parentMinValue);
        dfs(root.right, parentMaxValue, parentMinValue);
    }


    // 2529. 正整数和负整数的最大计数
    public int maximumCount(int[] nums) {
        int pos = 0, neg = 0;
        for (int x : nums) {
            if (x > 0) pos++;
            else if (x < 0) neg++;
        }
        return Math.max(pos, neg);
    }



    // 2923. 找到冠军 I
    public int findChampion(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            // 对于任意两个队伍，都存在强弱关系
            // 若其中某只队伍是冠军，则它是最强的，因此第 i 行所有值为1
            boolean isWin = true;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && i != j) {
                    isWin = false;
                    break;
                }
            }
            if (isWin) return i;
        }
        return -1;
    }


    // 2192. 有向无环图中一个节点的所有祖先
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        // 1. 记录各节点的出度(正向遍历)
        List<Integer>[] outs = new List[n];
        Arrays.setAll(outs, i -> new ArrayList<>());
        for (int[] e : edges) {
            outs[e[0]].add(e[1]);
        }

        // 2. 从 0 ~ n-1 号节点开始依次进行 dfs
        // 每次 dfs(第i个节点开始)经过的结点，将 i 号节点加入经过节点的祖先节点集合
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) res.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            boolean[] vis = new boolean[n];
            dfs(i, vis, outs, i, res);
        }
        return res;
    }

    private void dfs(int i, boolean[] vis, List<Integer>[] outs, int ancestor, List<List<Integer>> res) {
        vis[i] = true;
        if (i != ancestor) res.get(i).add(ancestor);

        for (int x : outs[i]) {
            if (!vis[x]) {
                dfs(x, vis, outs, ancestor, res);
            }
        }
    }

    //public List<List<Integer>> getAncestors(int n, int[][] edges) {
    //        // 1. 记录各节点的出度(反向遍历)
    //        List<Integer>[] outs = new List[n];
    //        Arrays.setAll(outs, i -> new ArrayList<>());
    //        for (int[] e : edges) {
    //            outs[e[1]].add(e[0]);
    //        }
    //
    //
    //        // 2. 从每个节点开始进行 dfs，所经过的节点即为该节点的祖先
    //        List<List<Integer>> res = new ArrayList<>();
    //        for (int i = 0; i < n; i++) {
    //            boolean[] vis = new boolean[n];
    //            dfs(i, vis, outs);
    //            vis[i] = false;
    //
    //            // vis[j] == true 即为 i 的祖先,从 0 开始遍历 vis保证了父节点由小到大排序
    //            res.add(new ArrayList<>());
    //            for (int j = 0; j < n; j++) {
    //                if (vis[j]) res.get(i).add(j);
    //            }
    //        }
    //        return res;
    //    }
    //
    //    private void dfs(int i, boolean[] vis, List<Integer>[] outs) {
    //        vis[i] = true;
    //        for (int x : outs[i]) {
    //            if (!vis[x]) {
    //                dfs(x, vis, outs);
    //            }
    //        }
    //    }

}
